package com.maltys.greedy;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/jump-game-ii/">跳跃游戏 II</a>
 */
public class JumpGameII {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }
        // 当前能跳到的最远位置
        int maxReach = 0;
        // 当前步数能跳到的最远位置
        int currentReach = 0;
        // 跳跃次数
        int jumps = 0;

        for (int i = 0; i < n - 1; i++) {
            // 更新当前能跳到的最远位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 如果到达当前步数能跳到的最远位置
            if (i == currentReach) {
                // 跳跃次数加1
                jumps++;
                // 更新当前步数能跳到的最远位置
                currentReach = maxReach;
            }
            // 如果已经可以到达终点
            if (currentReach >= n - 1) {
                return jumps;
            }
        }
        // 理论上不会到达这里，因为题目保证了可以跳到终点
        return 0;
    }


    public static void main(String[] args) {
        JumpGameII gameII = new JumpGameII();
        int jump = gameII.jump(new int[]{7, 0, 9, 6, 9, 6, 1, 7, 9, 0, 1, 2, 9, 0, 3});
        System.out.println(jump);
    }
}
